/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/subarray-sum
   @Language: C++
   @Datetime: 16-02-09 05:19
   */

class Solution {
public:
	/**
	 * @param nums: A list of integers
	 * @return: A list of integers includes the index of the first number 
	 *          and the index of the last number
	 * Tip: assume range [i,j] sum is 0,
	 *      then sum of [0,i-1] equal to sum of [0,j].
	 *      add sum of [0,i-1] to hashmap, find sum of [0,j]
	 *      if exists, return range [i-1+1,j].
	 */
	vector<int> subarraySum(vector<int> nums){
		// write your code here
		unordered_map<int,int> hm={{0,-1}};
		for(int i=0, sum=0; i<nums.size(); ++i){
			sum += nums[i];
			const auto &it = hm.find(sum);
			if (it==hm.end()) hm[sum]=i;
			else return {it->second+1,i};
		}
		return {};
	}
};
